package leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Cheng Jun
 * Description: 给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
 * <p>
 * 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
 * https://leetcode-cn.com/problems/pascals-triangle/
 * @version 1.0
 * @date 2021/12/29 14:38
 * 字节面试题
 */
public class generate {

    public static void main(String[] args) {
        generate.generate(4);
    }

    // 1 <= numRows <= 30
    // 输入: numRows = 5
    // 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
    //         1
    //       1   1
    //     1   2   1
    //   1   3    3   1
    // 1   4    6   4   1
    static public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> firstList = new ArrayList<>();
        firstList.add(1);
        res.add(firstList);
        for (int i = 1; i < numRows; i++) {
            List<Integer> preList = res.get(i - 1);
            // 初始化时，设置数组大小，避免扩容
            List<Integer> curList = new ArrayList<>(preList.size() + 1);
            // 第一个元素为 1
            curList.add(1);
            for (int j = 0; j < preList.size() - 1; j++) {
                // 设置下一行的中间元素
                curList.add(preList.get(j) + preList.get(j + 1));
            }
            // 最后一个元素为 1
            curList.add(1);
            res.add(curList);
        }
        return res;
    }
}
